// https://leetcode.cn/problems/string-matching-in-an-array/
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
		if(words.size() <= 1) return {};
		string s = "," + words[0];
		unordered_map<int, int> um;
		um.insert({0, 1});
		
		for(int i = 1; i < words.size(); i++){
			s = s + "," + words[i];
			um.insert({i, um[i - 1] + words[i - 1].size() + 1});
		}

		vector<string> res;
		// cout << s <<endl;
		// cout << s.find("mass") << endl;
		for(int i = 0; i < words.size(); i++){
			// cout << words[i] << "-" << s.find(words[i]) << "-" << um[i] << "-" << s.find(words[i], um[i] + 1) << endl;
			if(s.find(words[i]) != um[i]
			|| s.find(words[i], um[i] + 1) != string::npos
			){
				res.push_back(words[i]);
			}
		}
		
		return res;
    }
};

int main(){
	Solution so;
	vector<string> words = {"mass","as","hero","superhero"};
	auto res = so.stringMatching(words);
	for(auto i : res){
		cout << i << ",";
	}
	cout << endl;
	return 0;
}